package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-27
 * Time:16:44
 */

/**
 * 牛客算法篇:BM14 链表的奇偶重排
 描述
 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
 注意是节点的编号而非节点的数值。
 数据范围：节点数量满足 0≤n≤1050≤n≤105，节点中的值都满足 0≤val≤10000≤val≤1000
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 示例1
 输入：
 {1,2,3,4,5,6}
 返回值：
 {1,3,5,2,4,6}
 说明：
 1->2->3->4->5->6->NULL
 重排后为
 1->3->5->2->4->6->NULL
 */
public class oddEvenList {
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if (head == null) return null;
        ListNode cur = head.next,pre = head,even = cur;
        while (cur != null && cur.next != null){
           pre.next = cur.next;
           pre = pre.next;
           cur.next = pre.next;
           cur = cur.next;
        }
        pre.next = even;
        return head;
    }
}
